package T11_20;

public class T12 {
    /*思路：
    * 1 用数组统计s和t字符串每个字符出现次数
    * 2 滑动窗口在s中遍历，用i和j作为当前窗口左右边界
    * 3 如果当前窗口匹配到的字符种类数等于t中字符出现种类数时，尝试缩小窗口
    * */

    //定义最小窗口左右边界
    static int l,r;
    public String minWindow(String s, String t) {
        //保存两个字符串字符出现次数

        int[] sCount=new int[128];  //用于保存当前滑动窗口字符出现次数
        int[] tCount=new int[128];
        l=0;
        r=100000;
        char[] cs = s.toCharArray();
        char[] ts = t.toCharArray();
        //统计t中字符出现次数
        for (char c : ts) {
            tCount[c]++;
        }
        //统计t中不同字符个数
        int pass=0;
        for (int i : tCount) {
            if (i>0)
                pass++;
        }
        //使用滑动窗口遍历s，i和j为当前窗口左右边界
        //passed表示已经匹配的字符种类数
        int i=0,j=0;
        int passed=0;
        //找最小窗口
        while (j < s.length()) {
            char right = cs[j];
            sCount[right]++;
            //如果当前字符在当前窗口中出现的次数等于在t中出现的次数，就让passed加一
            if (sCount[right]==tCount[right]){
                passed++;
            }
            //如果匹配到的字符数量和t中出现的字符数量相等且值也相等，尝试缩小窗口
            while (passed==pass){
                //更新最小窗口左右边界
                if (r-l>j-i){
                    l=i;
                    r=j;
                }
                //尝试缩小窗口，移动左指针
                char left=cs[i];
                sCount[left]--;
                //如果当前左边界字符被移除后，当前窗口符合要求的字符数目小于tCount中字符left的出现次数
                //说明不能移动左指针
                if (sCount[left]<tCount[left]){
                    passed--;
                }
                i++;

            }
            j++;
        }
        return r-l==100000?"":new String(cs,l,r-l+1);

    }
}
